package com.zjsru.plan2024.oneday;

import com.zjsru.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 二叉搜索树的最近公共祖先
 * @Author: cookLee
 * @Date: 2024-02-25
 */
public class LowestCommonAncestor {

    /**
     * 主
     * \
     * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
     * 输出: 6
     * 解释: 节点 2 和节点 8 的最近公共祖先是 6。
     * \
     * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
     * 输出: 2
     * 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        LowestCommonAncestor lowestCommonAncestor = new LowestCommonAncestor();
        TreeNode root = new TreeNode(6, new TreeNode(2, new TreeNode(0), new TreeNode(4, new TreeNode(3), new TreeNode(5))), new TreeNode(8, new TreeNode(7), new TreeNode(9)));
        TreeNode p = new TreeNode(2);
        TreeNode q = new TreeNode(8);
        System.out.println(lowestCommonAncestor.lowestCommonAncestor(root, p, q));
    }


    /**
     * 二叉搜索树的最近公共祖先
     *
     * @param root 根
     * @param p    p
     * @param q    q
     * @return {@link TreeNode}
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = this.helper(root,p);
        List<TreeNode> pathQ = this.helper(root,q);
        //定义一个公共祖先，root即是最大的公共节点
        TreeNode ancestor  = null;
        for (int i = 0; i < pathP.size() && i < pathQ.size(); i++) {
            if (pathP.get(i) == pathQ.get(i)) {
                ancestor = pathP.get(i);
            } else {
                break;
            }
        }
        return ancestor;
    }

    /**
     * 帮手:目标节点到根节点的路径
     *
     * @param root   根
     * @param target 目标
     * @return {@link List}<{@link TreeNode}>
     */
    private List<TreeNode> helper(TreeNode root, TreeNode target) {
        List<TreeNode> path = new ArrayList<>();
        TreeNode node = root;
        while (node != target) {
            path.add(node);
            if (target.val < node.val) {
                //如果当前节点的值大于 target 的值，说明 target 应该在当前节点的左子树，因此将当前节点移动到它的左子节点；
                node = node.left;
            } else {
                //如果当前节点的值小于 target 的值，说明 target 应该在当前节点的右子树，因此将当前节点移动到它的右子节点。
                node = node.right;
            }
        }
        //记录最后一个节点
        path.add(node);
        return path;
    }

}
